The present invention relates to an information processing device and an information processing method that registers data into a data table where first item data is registered along with corresponding second item data, and retrieve the second item data corresponding to the first item data from the data table, and further relates to a program that enables a computer to function as such an information processing device, a data structure possessed by such an information processing device, a computer-readable recording medium recording therein such a program, and a computer-readable recording medium storing therein such a data structure.
Conventionally, in the field of network switch products such as L2 switches or L3 switches, there has been known such a system that can support more than a hundred and several tens of thousands of MAC addresses. The system can support many servers and clients, while, for identifying a corresponding destination port from a MAC address of a received packet, it is necessary to search through all MAC addresses held for that purpose to thereby retrieve the corresponding destination port.
In view of this, the system is configured so as to be able to search the MAC addresses at high speed using a hash method. Specifically, a MAC address table storing therein MAC addresses and destination ports in a corresponding relationship is prepared so as to be directly accessible by a hash key obtained by applying a hash function to a MAC address and, when a packet is received, a corresponding destination port can be identified using a hash key obtained based on a MAC address in the packet (e.g. see Patent Literature 1). In this event, when the same hash key is obtained from different MAC addresses, data corresponding to those MAC addresses are stored using chaining or the like and, upon retrieval, they are accessed using the common hash key and tracing chaining pointers.
However, inasmuch as there exist no complete hash functions, using any hash function can not avoid dispersion of data like many MAC addresses correspond to a particular hash key. Such data dispersion prevents an efficient search through the MAC addresses. It is, therefore, the present state wherein every time data is changed, the whole table is reprepared using a different hash function.
Particularly, when connection places are not fixed like mobile products, it is possible that a relationship between MAC addresses and ports of a switch or router changes momentarily, and addition and deletion of data relative to a MAC address table are constantly repeated. Therefore, inasmuch as averaging of data variance by the use of a hash function breaks down following the addition and deletion of data in the MAC address table, it is necessary to frequently perform sorting of data by changing hash function.
In case of a large-scale switch wherein the number of entries in a MAC address table exceeds a hundred and several tens of thousands, it takes a long time to calculate hash values again and sort data following the change of a hash function. Therefore, in effect, the change of the hash function requiring recalculation of hash values and sorting of data is not carried out. Specifically, it is the present state that when the number of entries in a memory area of addresses corresponding to a hash value exceeds an allowable value, entries are prevented from increasing with respect to such a hash value, while broadcast is used for dealing therewith. Since the broadcast is for transferring the same data over the network, it disables transmission of other packets to thereby extremely lower the network efficiency. In contrast, when it is configured to enter data corresponding to all MAC addresses, it is necessary to repeat many times a search that traces pointers, and therefore, a search time is prolonged.